#ifndef __QUADTREE_H__
#define __QUADTREE_H__

#include <queue>

#include "common.h"

enum quadrant
{
    BOT_LEFT = 0,
    BOT_RIGHT = 1,
    TOP_RIGHT = 2,
    TOP_LEFT = 3
};

typedef struct bounding_box
{
    double x;
    double y;
    double length; 
} bounding_box;

typedef struct quadtree_node
{
    long id;
    bounding_box *box;
    quadtree_node *parent;
    int num_children;
    quadtree_node *children[4];
    long num_particles;
    particle_t *particle;
    double com_x;
    double com_y;
    double total_mass;
    int level;
    quadrant q;
} quadtree_node;

typedef queue< quadtree_node * > quad_queue;
int is_leaf( quadtree_node *node );
bounding_box* quadrant_bounding_box( quadrant q, quadtree_node *node );
quadrant particle_quadrant( particle_t *p, quadtree_node *node );
void create_child( quadtree_node *node, quadrant q );
void create_children( quadtree_node *node );
void quad_insert( particle_t *particle, quadtree_node *node );
void eliminate_empty( quadtree_node *root );
void init_root( quadtree_node *root, double size );
void build_quadtree( quadtree_node *root, particle_t *particles, int n, double size );
void print_quadtree( quadtree_node *root );
void print_particles( particle_t *p, int n );

#endif
